package lcr;

import java.util.ArrayDeque;
import java.util.Deque;

public class Test0055 {
    public static void main(String[] args) {
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode15 = new TreeNode(15);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode20 = new TreeNode(20);
        treeNode15.left=treeNode9;
        treeNode15.right=treeNode20;
        treeNode7.left=treeNode3;
        treeNode7.right=treeNode15;

        BSTIterator bstIterator = new BSTIterator(treeNode7);
        while (bstIterator.hasNext()){
            System.out.println(bstIterator.next());
        }
    }
}


class BSTIterator {

    Deque<TreeNode> stack=new ArrayDeque<>();
    TreeNode cur;

    public BSTIterator(TreeNode root) {
        cur=root;
        dfs();
    }

    private void dfs() {
        while (cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        if (!stack.isEmpty()) cur=stack.pop();
    }

    public int next() {
        int val = cur.val;
        cur=cur.right;
        dfs();
        return val;
    }

    public boolean hasNext() {
        return cur!=null;
    }
}